package lc;


public class GasStation {

    public int canCompleteCircuit(int[] gas, int[] cost) {
    	int i=0;
    	while (i < gas.length) {
    		int net = gas[i]-cost[i];
			if (net >= 0) {
				int fail = trySol(gas, cost, i);
				if (fail < 0) {
					return i;
				}
				else if (fail < i){
					return -1;
				}
				else {
					i = fail;
				}
			}
			i++;
    	}
    	
    	return -1;
    }

	int trySol(int[] gas, int[] cost, int idx) {
		int tank=0;
    	for (int i=0; i<gas.length; i++) {
    		tank += gas[idx];
    		tank -= cost[idx];
    		if (tank < 0) {
    			return idx;
    		}
    		idx = (idx + 1) % gas.length;
    	}
		return -1;
	}

//	public int canCompleteCircuit(int[] gas, int[] cost) {
//	    // IMPORTANT: Please reset any member data you declared, as
//	    // the same Solution instance will be reused for each test case.
//	    int tank = 0;
//	    int counter = 0;
//	    int curIndex = 0;
//	    int ret = 0;
//	    boolean reset = true;
//	    while(tank >= 0 && counter < gas.length){
//	        if(reset){
//	            if(gas[curIndex]-cost[curIndex]>=0){
//	                tank += gas[curIndex]-cost[curIndex];
//	                counter++;
//	                ret = curIndex;
//	                reset = false;
//	            }
//	            else if(curIndex == gas.length-1) return -1;
//	            curIndex++;
//	        }
//	        else{
//	            tank+=gas[curIndex]-cost[curIndex];
//	            if(tank < 0){
//	                if(ret == gas.length-1) return -1;
//	                tank = 0;
//	                counter = 0;
//	                ret = curIndex;
//	                reset = true;
//	            }
//	            else{
//	                counter++;
//	                curIndex++;
//	            }
//	        }
//	        if(curIndex == gas.length) curIndex = 0;
//	    }
//	    return ret;
//	}
	
	public static void main(String ...strings) {
    	GasStation sol = new GasStation();
    	int canCompleteCircuit = sol.canCompleteCircuit(new int [] {1,2,3,3}, new int [] {2,1,5,1});
    	System.out.println(canCompleteCircuit);
    	
    	canCompleteCircuit = sol.canCompleteCircuit(new int [] {2,4}, new int [] {3,4});
    	System.out.println(canCompleteCircuit);
    }
}
